<?php
/**
 * @title 109. 有序链表转换二叉搜索树 - 递归
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head) {
        /**
         * @since 2020-08-18 极端情况排除
         */
        if($head === null){
            return null;
        } else {}

        /**
         * @since 2020-08-18 数组
         */
        $datas = [];

        /**
         * @since 2020-08-18 遍历链表
         */
        while($head !== null){
            $datas[] = $head->val;
            $head = $head->next;
        }

        /**
         * @since 2020-08-18 高度平衡的二叉树
         * @return
         */
        return self::find($datas, 0, count($datas)-1);
    }

    /**
     * @title 数组转高度平衡的二叉搜索树
     * @author start2004
     * @since 2020-08-18 Created
     *
     * @param array $datas
     * @param int $left
     * @param int $right
     */
    public function find($datas = [], $left = 0, $right = 0){
        /**
         * @since 2020-08-18 中间值
         */
        $mid = ($left+$right)>>1;

        /**
         * @since 2020-08-18 二叉树
         */
        $root = new TreeNode($datas[$mid]);

        /**
         * @since 2020-08-18 左子树
         */
        if($left !== $mid){
            $root->left = self::find($datas, $left, $mid-1);
        } else {}

        /**
         * @since 2020-08-18 右子树
         */
        if($right !== $mid){
            $root->right = self::find($datas, $mid+1, $right);
        } else {}

        /**
         * @return
         */
        return $root;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.18.php
 */
$datas = [
    [-10, -3, 0, 5, 9],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->sortedListToBST($xhprof->listNode($data));
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}
$xhprof->end();
